package com.bigshen.algorithm.dBinarySearch.solution01BinarySearch;

/**
 * 704. Binary Search 二分法
 * Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
 *
 * Example 1:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 *
 * Example 2:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinarySearch {

    // 一个完整的上升区间，二分法取中间值，
    // 如果target大于中位值，表明位于中位值右侧，起点左移 start -->
    // 如果target小于中位值，表明位于中位值左侧，终点左移  <-- end
    public int getIndex(int[] array, int target) {

        if (null == array || array.length == 0) {
            return -1;
        }
        // 1/3/5/7
        int start = 0;
        int end = array.length-1;

        while (end > start+1) {
            int mid = start + (end-start)/2;
            System.out.println(String.format("本地定位mid为 %s", array[mid]));
            if (target < array[mid]) {
                // target在左区间，尾部左移
                end = mid;
            } else if (array[mid] < target) {
                // target在右区间，头部右移
                start = mid;
            } else {
                return mid;
            }
        }

        if (array[start] == target) {
            return start;
        }

        if (array[end] == target) {
            return end;
        }

        return -1;

    }


    public static void main(String[] args) {

        int[] array = {1,2,3,5,7,9,12};

        System.out.println(new BinarySearch().getIndex(array, 12));

    }

}
